package zuo.algo.c07;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

import java.util.LinkedList;

/**
 * 00:20-判断一颗树是否是完全二叉树
 * 层序遍历时：
 *  1. 如果任一节点有右孩子，无左孩子，则返回False。
 *  2. 如果遇到第一个没有左孩子或右孩子的节点，后续都是叶子节点。
 */
public class TestCST {

    public static boolean isCST(TreeNode head) {
        if (head == null) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(head);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (left == null && right != null) {
                return false;
            }
            if (leaf) {
                if (left != null || right != null) {
                    return false;
                }
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }
            if (left == null || right == null) {
                leaf = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode head = TreeUtils.getTree();
        boolean cst = isCST(head);
        System.out.println(cst);
        head.right.right.right = null;
        cst = isCST(head);
        System.out.println(cst);
    }
}
